home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Mac Game Programming Gurus / TricksOfTheMacGameProgrammingGurus.iso / More Source / C⁄C++ / Peter's Final Project / src / maze.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-10  |  6.9 KB  |  361 lines  |  [TEXT/KAHL]
  1. /*
  2.  *  Peter's Final Project -- A texture mapping demonstration
  3.  *  © 1995, Peter Mattis
  4.  *
  5.  *  E-mail:
  6.  *  petm@soda.csua.berkeley.edu
  7.  *
  8.  *  Snail-mail:
  9.  *   Peter Mattis
  10.  *   557 Fort Laramie Dr.
  11.  *   Sunnyvale, CA 94087
  12.  *
  13.  *  Avaible from:
  14.  *  http://www.csua.berkeley.edu/~petm/final.html
  15.  *
  16.  *  This program is free software; you can redistribute it and/or modify
  17.  *  it under the terms of the GNU General Public License as published by
  18.  *  the Free Software Foundation; either version 2 of the License, or
  19.  *  (at your option) any later version.
  20.  *
  21.  *  This program is distributed in the hope that it will be useful,
  22.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  23.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  24.  *  GNU General Public License for more details.
  25.  *
  26.  *  You should have received a copy of the GNU General Public License
  27.  *  along with this program; if not, write to the Free Software
  28.  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  29.  */
  30.  
  31. #include <assert.h>
  32. #include <stdlib.h>
  33. #include <stdio.h>
  34.  
  35. #include "list.h"
  36. #include "maze.h"
  37. #include "sys.stuff.h"
  38. #include "utils.h"
  39.  
  40. /*
  41.  * A private type declaration.
  42.  */
  43. typedef struct {
  44.     short x, y;
  45. } WALL;
  46.  
  47. /*
  48.  * Declare the functions private to this module.
  49.  */
  50.  
  51. static WALL *make_wall (short, short);
  52. static void free_wall (WALL *);
  53. static void add_wall (WALL *);
  54. static WALL *random_wall (short);
  55.  
  56. /*
  57.  * Make a maze object.
  58.  */
  59.  
  60. MAZE
  61. make_maze ()
  62. {
  63.     MAZE maze;
  64.  
  65.     maze = (MAZE) ALLOC (sizeof (struct _MAZE));
  66.  
  67.     maze->data = NULL;
  68.     maze->size = 0;
  69.  
  70.     return maze;
  71. }
  72.  
  73. /*
  74.  * Free a maze object.
  75.  */
  76.  
  77. void
  78. free_maze (maze)
  79.     MAZE maze;
  80. {
  81.     if (maze)
  82.         FREE (maze->data);
  83.     FREE (maze);
  84. }
  85.  
  86. /*
  87.  * Initialize a maze to the given size. The seed value
  88.  *  is used to initialize the random number generator
  89.  *  which allows use to generate random mazes of virtually
  90.  *  any size. 
  91.  */
  92.  
  93. void
  94. maze_init (maze, size, seed)
  95.     MAZE maze;
  96.     short size;
  97.     long seed;
  98. {
  99.     short i, j;
  100.     short wall_count;
  101.     short cell_count;
  102.     short id_search;
  103.     short id_replace;
  104.     WALL *wall;
  105.  
  106.     if (maze == NULL)
  107.         fatal_error ("NULL maze passed to maze_init");
  108.     if (size < 3)
  109.         fatal_error ("Maze size too small -- %d", size);
  110.  
  111.     /*
  112.      * Even maze sizes are unwanted. (Try commenting this
  113.      *  out to see why).
  114.      */
  115.     if ((size % 2) == 0)
  116.     {
  117.         printf ("maze size is even (%d)...making it odd(%d)\n", size, size + 1);
  118.         size++;
  119.     }
  120.  
  121.     /*
  122.      * Set the maze size and allocate the data array.
  123.      */
  124.     maze->size = size;
  125.  
  126.     maze->data = (MAZE_CELL *) ALLOC (sizeof (MAZE_CELL) * maze->size * maze->size);
  127.  
  128.     /*
  129.      * Initialize every element to FALSE. That is, to empty.
  130.      * Give each element a unique id.
  131.      */
  132.     for (i = 0; i < maze_size (maze); i++)
  133.         for (j = 0; j < maze_size (maze); j++)
  134.         {
  135.             set_maze_element_state (maze, i, j, FALSE);
  136.             set_maze_element_id (maze, i, j, i * maze_size (maze) + j);
  137.         }
  138.  
  139.     /*
  140.      * Turn the edges on.
  141.      */
  142.     for (i = 0; i < maze->size; i++)
  143.     {
  144.         set_maze_element_state (maze, i, 0, TRUE);
  145.         set_maze_element_state (maze, 0, i, TRUE);
  146.         set_maze_element_state (maze, i, maze_size (maze) - 1, TRUE);
  147.         set_maze_element_state (maze, maze_size (maze) - 1, i, TRUE);
  148.     }
  149.  
  150.     /*
  151.      * Fill in the walls. Certain walls should never be removed
  152.      *  so don't add them to the wall list. Also, only increment
  153.      *  the wall count if a wall is added to the list.
  154.      */
  155.     wall_count = 0;
  156.     for (i = 1; i < maze_size (maze) - 1; i++)
  157.     {
  158.         for (j = 1; j < maze_size (maze) - 1; j++)
  159.         {
  160.             if (((i + j) % 2) == 1)
  161.             {
  162.                 set_maze_element_state (maze, i, j, TRUE);
  163.                 add_wall (make_wall (i, j));
  164.                 wall_count++;
  165.             }
  166.             else if (((i % 2) == 0) || ((j % 2) == 0))
  167.             {
  168.                 set_maze_element_state (maze, i, j, TRUE);
  169.             }
  170.         }
  171.     }
  172.  
  173.     /*
  174.      * Seed the random number generator.
  175.      */
  176.     srand (seed);
  177.  
  178.     /*
  179.      * The goal here is to take all the disconnected cells in the
  180.      *  maze and connect them by removing random walls. Each cell
  181.      *  can be thought of as a group of cells. We start off with
  182.      *  each cell being in its own group. As walls are knocked out
  183.      *  groups are joined until in the end we have one big group.
  184.      * This is really one of the best maze generation algorithms
  185.      *  around.
  186.      */
  187.     cell_count = (maze_size (maze) >> 1) * (maze_size (maze) >> 1);
  188.     while (cell_count > 1)
  189.     {
  190.         wall = random_wall (wall_count--);
  191.  
  192.         if ((wall->x % 2) == 0)
  193.         {
  194.             if (maze_element_id (maze, wall->x - 1, wall->y) !=
  195.                 maze_element_id (maze, wall->x + 1, wall->y))
  196.             {
  197.                 cell_count--;
  198.                 set_maze_element_state (maze, wall->x, wall->y, FALSE);
  199.  
  200.                 id_search = maze_element_id (maze, wall->x + 1, wall->y);
  201.                 id_replace = maze_element_id (maze, wall->x - 1, wall->y);
  202.  
  203.                 for (i = 1; i < maze_size (maze) - 1; i++)
  204.                     for (j = 1; j < maze_size (maze) - 1; j++)
  205.                         if (maze_element_id (maze, i, j) == id_search)
  206.                             set_maze_element_id (maze, i, j, id_replace);
  207.             }
  208.         }
  209.         else if ((wall->y % 2) == 0)
  210.         {
  211.             if (maze_element_id (maze, wall->x, wall->y - 1) !=
  212.                 maze_element_id (maze, wall->x, wall->y + 1))
  213.             {
  214.                 cell_count--;
  215.                 set_maze_element_state (maze, wall->x, wall->y, FALSE);
  216.  
  217.                 id_search = maze_element_id (maze, wall->x, wall->y + 1);
  218.                 id_replace = maze_element_id (maze, wall->x, wall->y - 1);
  219.  
  220.                 for (i = 1; i < maze_size (maze) - 1; i++)
  221.                     for (j = 1; j < maze_size (maze) - 1; j++)
  222.                         if (maze_element_id (maze, i, j) == id_search)
  223.                             set_maze_element_id (maze, i, j, id_replace);
  224.             }
  225.         }
  226.     }
  227. }
  228.  
  229. /*
  230.  * Print a description of a maze.
  231.  */
  232.  
  233. void
  234. maze_describe (maze)
  235.     MAZE maze;
  236. {
  237.     short i, j;
  238.  
  239.     assert (maze);
  240.     assert (maze->data);
  241.  
  242.     for (i = 0; i < maze_size (maze); i++)
  243.     {
  244.         for (j = 0; j < maze_size (maze); j++)
  245.         {
  246.             if (maze_element_state (maze, i, j))
  247.                 printf ("**");
  248.             else
  249.                 printf ("  ");
  250.         }
  251.         printf ("\n");
  252.     }
  253. }
  254.  
  255. /*
  256.  * Keep a list of walls and a list of free walls.
  257.  */
  258. static LIST wall_list = NULL;
  259. static LIST free_wall_list = NULL;
  260.  
  261. /*
  262.  * Make a wall and initialize its values appropriately
  263.  */
  264.  
  265. static WALL *
  266. make_wall (x, y)
  267.     short x;
  268.     short y;
  269. {
  270.     WALL *wall;
  271.     LIST list;
  272.  
  273.     if (free_wall_list)
  274.     {
  275.         wall = list_datum (wall_list);
  276.  
  277.         list = wall_list;
  278.         wall_list = list_next (wall_list);
  279.  
  280.         free_list (list);
  281.     }
  282.     else
  283.     {
  284.         wall = (WALL *) ALLOC (sizeof (WALL));
  285.     }
  286.  
  287.     wall->x = x;
  288.     wall->y = y;
  289.  
  290.     return wall;
  291. }
  292.  
  293. /*
  294.  * Free a wall.
  295.  */
  296.  
  297. static void
  298. free_wall (wall)
  299.     WALL *wall;
  300. {
  301.      FREE (wall);
  302. }
  303.  
  304. /*
  305.  * Add a wall to the wall list.
  306.  */
  307.  
  308. static void
  309. add_wall (wall)
  310.     WALL *wall;
  311. {
  312.     LIST list;
  313.  
  314.     list = make_list ();
  315.     set_list_datum (list, wall);
  316.     set_list_next (list, wall_list);
  317.     wall_list = list;
  318. }
  319.  
  320. /*
  321.  * Pick a random wall from the wall list and
  322.  *  remove that wall from the list.
  323.  */
  324.  
  325. static WALL *
  326. random_wall (total)
  327.     short total;
  328. {
  329.     short n;
  330.     LIST t1, t2;
  331.     WALL *wall;
  332.  
  333.     n = rand () % total;
  334.  
  335.     if (n == 0)
  336.     {
  337.         wall = list_datum (wall_list);
  338.  
  339.         t1 = wall_list;
  340.         wall_list = list_next (wall_list);
  341.         free_list (t1);
  342.     }
  343.     else
  344.     {
  345.         t2 = wall_list;
  346.         t1 = list_next (wall_list);
  347.  
  348.         while (--n)
  349.         {
  350.             t2 = t1;
  351.             t1 = list_next (t1);
  352.         }
  353.  
  354.         wall = list_datum (t1);
  355.         set_list_next (t2, list_next (t1));
  356.         free_list (t1);
  357.     }
  358.  
  359.     return wall;
  360. }
  361.